//
// Description: 1014. 最佳观光组合
// Created by Loading on 2022/6/25.
//

#include <bits/stdc++.h>

using namespace std;

int maxScoreSightseeingPair(vector<int> &values) {
    int n = values.size();
    int res = 0;
    // 将 values[i] + values[j] + i - j 分成 values[i] + i 和 values[j] - j
    // values[j] - j 为固定值，_max 表示 values[i] + i 的最大值，遍历 j 取最大即可
    int _max = values[0] + 0;

    for (int j = 1; j < n; ++j) {
        res = max(res, _max + values[j] - j);
        // 更新 _max
        _max = max(_max, values[j] + j);
    }

    return res;
}

int main() {
    vector<int> values{8, 1, 5, 2, 6};

    int res = maxScoreSightseeingPair(values);

    cout << res << endl;

    return 0;
}
